package 算法_递归分治;

import java.util.Arrays;

public class Heap_Sort {
    public static void main(String[] args) {
        int[] a = {2, 4, 6, 7, 8, 4, 2, 5, 7, 98, 4, 2};
        heap_sort(a);
        System.out.println(Arrays.toString(a));
    }

    private static void heap_sort(int[] a) {
        for (int i = a.length / 2; i >= 0; i--)
            adjust_heap(a, i, a.length);
        for (int i = a.length - 1; i > 0; i--) {
            swap(a, 0, i);
            adjust_heap(a, 0, i);
        }
    }

    private static void swap(int[] a, int i, int j) {
        a[i] = a[i] ^ a[j];
        a[j] = a[i] ^ a[j];
        a[i] = a[i] ^ a[j];
    }

    private static void adjust_heap(int[] a, int p, int len) {
        int x = a[p];
        int ls = 2 * p + 1;
        while (ls < len) {
            ls = (ls + 1 < len && a[ls] < a[ls + 1]) ? ls + 1 : ls;
            if (a[ls] < x) break;
            a[p] = a[ls];
            p = ls;
            ls = 2 * p + 1;
        }
        a[p] = x;
    }
}
